package week_six;

public class JumpGameII_45 {
    public int jumpWithDP(int[] nums) {
        //DP,动规
        //状态 steps[i],到达i最小步数。
        //转移 steps[i] = min{steps[j]+1} (j<i);  j出发到达i，取步数最小的j.
        //目标 steps[n-1]最小。
        int length = nums.length;
        int[] steps = new int[length];
        steps[0] = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    if (steps[i] == 0) {
                        steps[i] = steps[j] + 1;
                    } else {
                        steps[i] = Math.min(steps[i], steps[j] + 1);
                    }
                }

            }
        }

        return steps[length - 1];
    }

    public int jump(int[] nums) {
        //贪心，往后多看一步
        //下一步能跳的最远的位置就是当前最优解。
        int ans = 0;
        int length = nums.length;
        int max = 0;
        int next = 0;

        for (int i = 0; i < length - 1; i++) {
            max = Math.max(max, i + nums[i]);
            if (i == next) {
                next = max;
                ans++;
            }
        }

        return ans;
    }
}
